home *** CD-ROM | disk | FTP | other *** search
/ Disc to the Future 2 / Disc to the Future Part II Programmer's Reference (Wayzata Technology)(6013)(1992).bin / MAC / MPW_C / SPELL__ / DAWG.H < prev    next >
Text File  |  1990-07-03  |  2KB  |  67 lines
  1. /**
  2. *
  3. *       DAWG.H
  4. *
  5. *       Header file for Directed Acyclic Word Graph access
  6. *
  7. *       The format of a DAWG node (8-bit arbitrary data) is:
  8. *
  9. *        31                24 23  22  21                                     0
  10. *       +--------------------+---+---+--+-------------------------------------+
  11. *       |      Letter        | W | N |??|            Node pointer             |
  12. *       +--------------------+---+---+--+-------------------------------------+
  13. *
  14. *      where N flags the last edge in a node and W flags an edge as the
  15. *      end of a word. 21 bits are used to store the node pointer, so the
  16. *      dawg can contain up to 262143 edges. (and ?? is reserved - all code
  17. *      generating dawgs should set this bit to 0 for now)
  18. *
  19. *      The root node of the dawg is at address 1 (because node 0 is reserved
  20. *      for the node with no edges).
  21. *
  22. *      **** PACKED tries do other things, still to be documented!
  23. *
  24. **/
  25.  
  26. #define TRUE (0==0)
  27. #define FALSE (0!=0)
  28.  
  29. #define DAWG_MAGIC 0x01234567
  30. #define PACK_MAGIC 0x34567890
  31.  
  32. #define TERMINAL_NODE 0
  33. #define ROOT_NODE 1
  34.  
  35. #define V_END_OF_WORD   23
  36. #define M_END_OF_WORD   (1L << V_END_OF_WORD)
  37. #define V_END_OF_NODE   22                     /* Bit number of N */
  38. #define M_END_OF_NODE   (1L << V_END_OF_NODE)   /* Can be tested for by <0 */
  39.  
  40.  
  41. #define V_FREE          22             /* Overloading this bit, as
  42.                                           packed tries need no end-of-node */
  43. #define M_FREE          (1L << V_FREE)
  44.  
  45. #define V_LETTER        24
  46. #define M_LETTER        0xFF
  47. #define M_NODE_POINTER  0x1FFFFFL     /* Bit mask for node pointer */
  48.  
  49. /* max_chars and base_chars are a hangover from the days when this
  50.    was trying to save space, and dawgs were only able to contain
  51.    characters in the range 'a'..'z' 'A'..'Z' (squeezed into 6 bits).
  52.    Now that we're '8-bit clean' we no longer need these.  Later code
  53.    in fact doesn't support the old style; but some procedures still
  54.    subtract 'BASE_CHAR' from the character to normalize it.  Since it
  55.    is now 0 it is a no-op... */
  56. #define MAX_CHARS       256
  57. #define BASE_CHAR       0
  58.  
  59. /* Enough? */
  60. #define MAX_WORD_LEN    256
  61.  
  62. #define MAX_LINE        256
  63.  
  64. typedef long NODE;
  65. typedef long INDEX;
  66.  
  67.